package 并查集;

//递归回溯里也有此题
public class No200岛屿数量 {

    /**
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     *
     * 示例 1：
     * 输入：grid = [
     *   ["1","1","1","1","0"],
     *   ["1","1","0","1","0"],
     *   ["1","1","0","0","0"],
     *   ["0","0","0","0","0"]
     * ]
     * 输出：1
     * 示例 2：
     * 输入：grid = [
     *   ["1","1","0","0","0"],
     *   ["1","1","0","0","0"],
     *   ["0","0","1","0","0"],
     *   ["0","0","0","1","1"]
     * ]
     * 输出：3
     */

    private int allLength;
    private int itemLength;

    public int numIslands(char[][] grid) {
        allLength = grid.length;
        if (allLength == 0) {
            return 0;
        }
        itemLength = grid[0].length;
        int size=allLength * itemLength;
        //多出来的是虚拟水地
        UnionFind unionFind = new UnionFind(size +1);
        int[][] directions = {{1, 0}, {0, 1}};
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if (grid[i][j] == '0') {
                    //水地和[虚拟水地连接] 注意范围是 [0,allLength * itemLength)
                    unionFind.union(itemLength*i+j,size);
                } else {
                    //陆地
                    for (int k = 0; k < 2; k++) {
                        int newX = i + directions[k][0];
                        int newY = j + directions[k][1];
                        /**
                         * 先 右下 延申,方便后面的地面照应上
                         */
                        if (newX < allLength && newY < itemLength && grid[newX][newY] == '1') {
                            //每合并非同一块地面一次,块就减少一个
                            unionFind.union(i * itemLength + j, newX * itemLength + newY);
                        }
                    }
                }
            }
        }
        //水地最终会汇集成一块   总块=(一块大水地和分散的陆地)
        return unionFind.getCount()-1;
    }

}
